package leetcode

import "container/heap"

//https://leetcode.cn/problems/network-delay-time/

/**
单源最短路径：Dijkstra算法
（1）Dijkstra算法必须指定一个源点s，且所有边权值没有负数
（2）生成一个s到各个点的最小距离表map，把(s, 0)记录放入小根堆
（3）从小根堆里弹出记录（y，w），表示当前从s到y，最小距离是w
（4）如果y是之前算过的点，重复步骤3）；
（5）如果y是之前没算过的点，记录map[y] = w；
	y的邻接点假设为{a,b,c}，
	如果a没最小距离的记录，把(a, w + y到a的代价)放入小根堆；否则跳过
	如果b没最小距离的记录，把(b, w + y到b的代价)放入小根堆；否则跳过
	如果c没最小距离的记录，把(c, w + y到c的代价)放入小根堆；否则跳过
	总之，y的所有邻接点，全按照上面处理后，重复步骤3）
（6）小根堆空了，过程停止
*/

// NetworkDelayTime 该函数用于计算网络延迟时间，输入参数包括：
//
//	times（传输关系和延迟时间的二维数组）、times[i] = (ui, vi, wi)，其中 ui 是源节点，vi 是目标节点， wi 是一个信号从源节点传递到目标节点的时间
//	n（网络中节点的数量）、
//	k（信号源节点）。
//	函数返回信号传递至所有节点所需的最短时间
func networkDelayTime(times [][]int, n int, k int) int {
	graph := make([][][]int, n)
	for _, time := range times {
		from := time[0] - 1
		to := time[1] - 1
		weight := time[2]

		graph[from] = append(graph[from], []int{to, weight})
	}

	minDistances := make([]int, n)
	for i := range minDistances {
		minDistances[i] = -1
	}

	minHeap := &MinHeap{}
	heap.Push(minHeap, Record{target: k - 1, totalWeight: 0})

	for minHeap.Len() > 0 {
		cur := heap.Pop(minHeap).(Record)
		if minDistances[cur.target] != -1 {
			continue
		}
		minDistances[cur.target] = cur.totalWeight
		for _, edge := range graph[cur.target] {
			to := edge[0]
			toWeight := edge[1]
			if minDistances[to] == -1 {
				heap.Push(minHeap, Record{to, cur.totalWeight + toWeight})
			}
		}
	}

	ans := 0
	for _, distance := range minDistances {
		if distance == -1 {
			return -1
		}
		ans = max(ans, distance)
	}
	return ans

}

type Record struct {
	target      int
	totalWeight int
}

type MinHeap []Record

func (h MinHeap) Len() int {
	return len(h)
}

func (h MinHeap) Less(i, j int) bool {
	return h[i].totalWeight < h[j].totalWeight
}

func (h MinHeap) Swap(i, j int) {
	h[i], h[j] = h[j], h[i]
}

func (h *MinHeap) Push(x interface{}) {
	*h = append(*h, x.(Record))
}

func (h *MinHeap) Pop() interface{} {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[:n-1]
	return x
}
